/*
 * @lc app=leetcode.cn id=45 lang=golang
 *
 * [45] 跳跃游戏 II
 */

// 5. 动态规划
// @lc code=start
func jump(nums []int) int {
	if len(nums) == 1 {
		return 0
	}
	dp := make([]int, len(nums))
	for i := 1; i < len(nums); i++ {
		dp[i] = math.MaxInt64
		for j := 0; j < i; j++ {
			if nums[j]+j >= i { // 前面的每一个是否能到当前下标，取最小值
				dp[i] = min(dp[i], dp[j]+1)
			}
		}
	}
	return dp[len(nums)-1]
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

// @lc code=end

// 4. 广度优先
// 在【3】的基础上把判断下沉，从大的开始遍历
// @lc code=start
func jump(nums []int) int {
	if len(nums) == 1 {
		return 0
	}

	history := make(map[int]bool)

	var bfs func(index []int, count int) int
	bfs = func(index []int, count int) int {
		if len(index) == 0 {
			return count
		}
		temp := []int{}
		for i := 0; i < len(index); i++ {
			for j := nums[index[i]]; j >= 1; j-- {
				if index[i]+j >= len(nums)-1 {
					return count + 1
				}

				if _, ok := history[index[i]+j]; !ok {
					temp = append(temp, index[i]+j)
					history[index[i]+j] = true
				}
			}
		}

		return bfs(temp, count+1)
	}
	return bfs([]int{0}, 0)
}

// @lc code=end

// 3. 广度优先 还是内存超了 86/109
// 在【2】的基础上加了history
// @lc code=start
func jump(nums []int) int {
	if len(nums) == 1 {
		return 0
	}

	history := make(map[int]bool)

	var bfs func(index []int, count int) int
	bfs = func(index []int, count int) int {
		temp := []int{}
		for i := 0; i < len(index); i++ {
			if index[i] >= len(nums)-1 {
				return count
			}
			for j := 1; j <= nums[index[i]]; j++ {
				if _, ok := history[index[i]+j]; !ok {
					temp = append(temp, index[i]+j)
					history[index[i]] = true
				}
			}
		}

		return bfs(temp, count+1)
	}
	return bfs([]int{0}, 0)
}

// @lc code=end

// 2. 广度优先 内存超了 82/109
// @lc code=start
func jump(nums []int) int {
	if len(nums) == 1 {
		return 0
	}

	var bfs func(index []int, count int) int
	bfs = func(index []int, count int) int {
		temp := []int{}
		for i := 0; i < len(index); i++ {
			if index[i] >= len(nums)-1 {
				return count
			}
			for j := 1; j <= nums[index[i]]; j++ {
				temp = append(temp, index[i]+j)
			}
		}

		return bfs(temp, count+1)
	}
	return bfs([]int{0}, 0)
}

// @lc code=end

// 1. 深度优先 超时 73/109
// @lc code=start
func jump(nums []int) int {
	if len(nums) == 1 {
		return 0
	}

	ans := math.MaxInt64
	var dfs func(index, count int)
	dfs = func(index, count int) {
		if index+nums[index] >= len(nums)-1 {
			ans = min(ans, count+1)
			return
		}
		for i := nums[index]; i > 0; i-- {
			dfs(index+i, count+1)
		}
	}
	dfs(0, 0)
	return ans
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

// @lc code=end

